МОДЕЛИ СОБЫТИЙНЫХ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
УПРАВЛЕНИЯ ВЗАИМОДЕЙСТВУЮЩИМИ ПРОЦЕССАМИ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ МЕХАНИЗМА МОНИТОРА 

Волчихин Владимир Иванович, доктор технических наук, профессор, президент Пензенского государственного университета (г. Пенза, ул. Красная, 40), rectorat@pnzgu.ru
Вашкевич Николай Петрович, доктор технических наук, профессор, кафедра вычислительной техники, Пензенский государственный университет (г. Пенза, ул. Красная, 40), vt@alice.pnzgu.ru
Бикташев Равиль Айнулович, кандидат технических наук, профессор, кафедра вычислительных машин и систем, Пензенская государственная технологическая академия (г. Пенза, проезд Байдукова, д. 1а), bra559620@sura.ru 

681.3.012 

Целью работы является создание методики формального описания алгоритма управления взаимодействующими параллельными процессами при обмене сообщениями между ними, выполняющимися с использованием механизма монитора, кольцевого буфера и типовой задачи «производители-потребители». В основу работы положен метод событийных недетерминированных автоматов (СНДА), позволяющий представить алгоритм управления в простой и компактной форме в виде системы рекуррентных канонических бескванторных уравнений, описывающих все реализуемые в системе управления частные события. Отличительная особенность метода СНДА заключается в том, что система уравнений, представляющая функции переходов в управляющем алгоритме, описывается не в терминах состояний детерминированных автоматов (ДА), а в терминах частных событий недетерминированных автоматов, одновременное существование которых и определяет состояние эквивалентного ему ДА. Так как число частных событий недетерминированных автоматов значительно меньше числа состояний эквивалентных ему ДА, то описание управляющего алгоритма на языке СНДА будет отличаться значительной простотой.
Представленная методика формального описания частных событий алгоритма управления передачей сообщений в распределенных и многопроцессорных системах на языке СНДА обеспечивает реализацию основных свойств, которыми должны обладать системы управления: отсутствие тупиковых ситуаций (бесконфликтность) и справедливость (отсутствие бесконечного ожидания и нахождения в мониторе процессов, обращающих к общему ресурсу). Аналитическое представление алгоритма управления взаимодействующими параллельными процессами в виде системы рекуррентных канонических бескванторных уравнений позволяет выполнить простую трансформацию описания алгоритма управления на языки описания аппаратуры (например, VHDL) для верификации алгоритма и его аппаратной реализации. 

Ключевые слова

алгоритм управления, взаимодействующие параллельные процессы, событийные недетерминированные автоматы, задача «производители – потребители», механизмы монитора. 

 Скачать статью в формате PDF

1. Дейтел, Г. Введение в операционные системы : в 2-х т. ; пер. с англ. / Г. Дейтел. – М. : Мир, 1987. – Т. 1. – 359 с.
2. Соловьев, Г. И. Операционные системы ЭВМ : учеб. пособие / Г. И. Соловьев, В. Д. Никитин. – М. : Высш. шк., 1988. – 207 с.
3. Hoare, C. A. R. Monitors, An Operating System Structuring Concept / C. A. R. Hoare // Erratum in Commun. Of the ACM. – 1975. – V. 18. – P. 95.
4. Brinch Hansen, P. The Programming Language Concurrent Pascal / P. Brinch Hansen // IEEE Trans. On Software Engineering. – 1975. – V. SE-1. – P. 199–207.
5. Эндрюс, Г. Р. Основы многопоточного и распределенного программирования : пер. с англ. / Г. Р. Эндрюс. – М. : Вильямс, 2003. – 512 с.
6. Таненбау м, Э. Современные операционные системы / Э. Таненбаум. – 2-е изд-е. – СПб. : Питер, 2002. – 1040 с.
7. Вашкевич, Н. П. Недетерминированные автоматы в проектировании систем параллельной обработки : учеб. пособие / Н. П. Вашкевич. – Пенза : Изд-во Пенз. гос. ун-та, 2004. – 280 с.
8. Вашкевич, Н. П. Формальное описание алгоритма управления взаимодействующими параллельными процессами в задаче «производители–потребители» с использованием кольцевого согласующего буфера / Н. П. Вашкевич, Р. А. Бикташев, А. А. Тараканов // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2007. – № 4. – С. 98–107.
9. Кларк, Э. М. Верификация моделей программы: Model Checking : пер. с англ. / Э. М. Кларк, О. Грамберг, Д. Пелед. – М. : МЦНМО, 2002. – 416 с.
10. Вашкевич, Н. П. Аппаратная реализация функций синхронизации параллельных процессов при обращении к разделяемому ресурсу на основе ПЛИС / Н. П. Вашкевич, Р. А. Бикташев, Е. И. Гурин // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2007.–№2.–С. 3–12.
11. Кейлингерт, П. Элементы операционных систем : пер. с англ. / П. Кейлингерт. – М. : Мир, 1985. – 295 с.